[POJ 3581]Sequence

原题链接：
题目大意：有一个长度为$n$的数列$\{a\}$，其中$a_1$严格大于数列中任意一个元素。现要将数列切割成三段，并反转每一段字符串，问能得到的字典序最小的串是什么。每一段元素不可以为空，也不能把数字切开。
数据范围：$1 \leq n \leq 200000$

样例输入：

5
10
1
2
3
4

样例输出

1
10
2
4
3

由于要分成三段，先考虑第一段是怎样的：由于说题目给了一个非常强的条件，即$a_1$是严格大于数列里其他任意元素的，所以第一段实际上很好考虑，划分出第一段反转之后最小的前缀就是整个字符串反转之后最小的后缀。这一步对整个反转的字符串做$SA$就可以求了。剩下的两段由于不独立，所以不能像第一段这样直接说找出这一节最短的就行。但是这个题肯定不会就这样搞一个第一问让你白做，联系一下两个问题可以做一个转换。假设说我们现在已经把第一段找出来，把他从$S$里抠出去了，剩下的两段就是在剩下的$S$里找一个分界线。之后的$S$都视作是已经抠完了第一段的剩下的部分。这里的$S_2$和$S_3$可以看做是整个$S$复制一遍接在后面，而$S$的反转部分就是接在一起之后中间的一小段。详见下图：

也就是说这个问题，又可以等价于是复制一遍$S$接在后面，再求一次$SA$之后求后缀字典序最小的答案。

代码：

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;
typedef long long ll;
const int N = 4e5+7;
int sa[N],lcp[N],a[N],rev[N];
namespace SA
{
	int rank[N],tmp[N];
	int n,k;
	bool sa_cmp(int i,int j)
	{
		if(rank[i] != rank[j])	return rank[i] < rank[j];
		else
		{
			int ri = i + k <= n ? rank[i + k] : -1;
			int rj = j + k <= n ? rank[j + k] : -1;
			return ri < rj;
		}
	}
	void build(int s[],int in_n)
	{
		n = in_n;
		for(int i = 0;i <= n;++i)
		{
			sa[i] = i;
			rank[i] = i < n ? s[i] : -1;
		}
		for(k = 1;k <= n;k *= 2)
		{
			sort(sa,sa + n + 1,sa_cmp);
			tmp[sa[0]] = 0;
			for(int i = 1;i <= n;++i)	tmp[sa[i]] = tmp[sa[i - 1]] + sa_cmp(sa[i - 1],sa[i]);
			for(int i = 0;i <= n;++i)	rank[i] = tmp[i];	
		}
	}
}

int main()
{
	int n;scanf("%d",&n);
	for(int i = 0;i < n;++i)	scanf("%d",&a[i]);
	reverse_copy(a,a + n,rev);
	SA::build(rev,n);
	// for(int i = 0;i < n;++i)	cout << sa[i] << " ";cout << endl;
	int p1;
	for(int i = 0;i < n;++i)
	{
		p1 = n - sa[i];
		if(p1 >= 1 && n - p1 >= 2)	break;
	}
	// cout << p1 << endl;
	int m = n - p1;
	reverse_copy(a + p1,a + n,rev);
	reverse_copy(a + p1,a + n,rev + m);
	SA::build(rev,m * 2);
	int p2;
	for(int i = 0;i <= 2 * m;++i)
	{
		p2 = p1 + m - sa[i];
		if(p2 - p1 >= 1 && n - p2 >= 1)	break;
	}
	// cout << p2 << endl;
	reverse(a,a + p1);
	// for(int i = 0;i < n;++i)	printf("%d\n",a[i]);puts("");
	reverse(a + p1,a + p2);
	reverse(a + p2,a + n);
	for(int i = 0;i < n;++i)	printf("%d\n",a[i]);
    return 0;
}